package com.sicheng.lc.周赛.分类.dfs记忆化;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/3 22:05
 */
public class 网格图中递增路径的数目 {

    //https://leetcode.cn/problems/number-of-increasing-paths-in-a-grid/
    static int m, n;
    static int mod = (int) (1e9 + 7);
    int[][] map;

    public int countPaths(int[][] grid) {
        init(grid);
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res = (res + dfs(i, j, grid)) % mod;
            }
        }
        return res;
    }

    static int[][] d = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

    int dfs(int i, int j, int[][] g) {
        if (map[i][j] > 0) {
            return map[i][j];
        }
        map[i][j] = 1;
        for (int[] direction : d) {
            int x = direction[0] + i;
            int y = direction[1] + j;
            if (x >= 0 && x < m && y >= 0 && y < n && g[x][y] > g[i][j]) {
                map[i][j] = (map[i][j] + dfs(x, y, g)) % mod;
            }
        }
        return map[i][j];
    }

    private void init(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        map = new int[m][n];
    }

    public static void main(String[] args) {
        int[][] g = {{1, 1}, {3, 4}};
        网格图中递增路径的数目 s = new 网格图中递增路径的数目();
        System.out.println(s.countPaths(g));
    }
}
